package leetcode;

import list.LinkedListCreate;
import list.ListNode;
import Tree.BinaryTreeCreate;
import Tree.TreeNode;

public class ConvertListOrArrayToTree {

	int times = 1;
	public static void main(String[] args) {
		int[] array = {-1,0,1,2};
		ListNode node = LinkedListCreate.createList(array);
		ConvertListOrArrayToTree inst = new ConvertListOrArrayToTree();
		TreeNode node2 = inst.sortedListToBST(node);
		BinaryTreeCreate.inOrder(node2);
	}
	//first problem convertArrayToTree  Problem 108
	public TreeNode sortedArrayToBST(int[] nums) {
        return build(0, nums.length - 1, nums);
    }
    public TreeNode build(int start, int end, int[] nums){
        if(start > end){
            return null;
        }
        int middle = (start + end) / 2;
        TreeNode root = new TreeNode(nums[middle]);
        root.left = build(start, middle - 1, nums);
        root.right = build(middle + 1, end, nums);
        return root;
    }
    
	//this problem is similar with array to BST, but the array we can get the middle element in O(1)
    //so can we think some method to change the listNode to get middle in O(logn)
    //yes two pointer does, while we use two pointer, one move two step, the other move one step
    //we can get the middle in the listNode
    public TreeNode sortedListToBST(ListNode head) {
        return build(head, null);
    }
    public TreeNode build(ListNode start, ListNode end){
        //while the two pointer is equal, that means we can return 
        //there we return null while start == end, beacause when we use listNode, we can't find the previous node
        //so we use mid to replace mid - 1, and then the problem is some node might duplicate 
        if(start == end){
            return null;
        }
        ListNode slow = start, fast = start;
        if(end != null){
        	System.out.println("end : " + end.val);
        }
        if(start != null){
        	System.out.println("start value: " + start.val);
        }
        //the first I write fast != null
        //actually it should be fast != end
        while(fast != end && fast.next != end){
            fast = fast.next.next;
            slow = slow.next;
        }
        // in that time slow point to the middle
        //but how can we find the previous node middle - 1
        //the key is we use slow ,and the while start equal end we just return null is ok
        TreeNode root = new TreeNode(slow.val);
        root.left = build(start, slow);
        root.right = build(slow.next, end);
        return root;
    }
}
